1. Field of the Invention
The present invention relates to the fields of computer operating systems, multi-processor hardware systems, and object oriented programming. Specifically, the present invention is a method and apparatus for handling interrupts in an operating system kernel which may accommodate multi-threading and real-time processing.
2. Background
A computer system can be generally divided into four components: the hardware, the operating system, the applications programs, and the users. The hardware (the central processing unit (CPU), memory, and input/output (I/O) devices) provides the basic computing resources. The application programs (database systems, games, business programs, etc.) define the ways in which these resources are used to solve the computing problems of the users. The operating system controls and coordinates the use of the hardware among the various application programs for the various users. In doing so, the primary goal of the operating system is to make the computer system convenient to use. A secondary goal is to use the hardware in an efficient manner.
In attempting to meet these goals, operating system designs have evolved through systems allowing multiprogramming, time-sharing (also called multi-tasking), distributed systems and real-time systems. With multiprogramming, several jobs are kept in memory at the same time and the CPU is switched back and forth between them to maximize the use of the CPU and to decrease the overall time required to complete all jobs. Time-sharing is an extension of multiprogramming where the CPU is switched between jobs so frequently that users may continue to interact with the jobs but the CPU again optimizes the use of its time to process another job while waiting on users to respond. Real-time operating systems are often used for dedicated control devices but more recently are being required in business systems to accommodate multimedia and other time dependent requirements. A real-time operating system has well-defined fixed-time constraints, during which the system must perform the required tasks or the system will fail.
A more recent trend is to distribute computation among several processors, called generally multi-processor systems. In a "tightly coupled" system, the processors share memory and a clock. In such systems, communication between processors takes place through shared memory. In a "loosely coupled" system, each processor has its own memory and clock and the processors communicate with each other through various communication channels such as high-speed buses or telephone lines. These latter systems are usually called "distributed systems". For further description of operating systems in general see "Operating System Concepts" by A. Silberschatz, J. Peterson, and P. Glavin, Addison Wesley 1991.
The UNIX.RTM. Operating System is currently used on thousands of computer systems throughout the world. UNIX is a registered trademark of UNIX System Laboratories, Inc. UNIX was designed to be a simple time-sharing system, with a hierarchical file system, which supported multiple "processes." A "process" is the execution of a program and consists of a pattern of bytes that the CPU interprets as machine instructions (text), data, and stack. (A "stack" is a set of hardware registers or a reserved amount of main memory that is used for arithmetic calculations or for keeping track of internal operations. Stacks usually work on a last-in-first-out basis; the last item, or address, placed (pushed) onto the stack is the first item removed (popped) from the stack). Several processes may be instances of a single program. Processes communicate with other processes and the kernel via "system calls." A process can execute in both "user" mode and "kernel" mode and so has a separate stack for each mode. The "context" of a process or its "state" is defined as:
its text, PA1 values of global user variables and data structures, PA1 values of registers, PA1 values stored in its process table slot and "u area", and PA1 the contents of its user and kernel stacks.
The "process table" and "u area" are both data structures which describe the state of the process. Switching from user mode to kernel mode in the same process does not require a "context switch", however when switching from process "A" to process "B" a context switch must be made. A "context switch" requires the kernel to save all of the registers and values so that when a process is reinitiated it will resume from the spot where it was executing when an earlier context switch was made.
UNIX consists of two separable parts: the "kernel" and the "systems programs." Systems programs consist of system libraries, compilers, interpreters, shells and other such programs which provide useful functions to the user. The kernel provides the file system, CPU scheduling, memory management, and other operating-system functions by responding to "system calls". Conceptually, the kernel sits between the hardware and the users. System calls are the means for the programmer to communicate with the kernel. System calls are made by a "trap" to a specific location in the computer hardware (sometimes called an "interrupt" location or vector). Specific parameters are passed to the kernel on the stack and the kernel returns with a code in specific registers indicating whether the action required by the system call was completed successfully or not. For more detailed information on the UNIX operating system see "The Design of the UNIX Operating System" by Maurice J. Bach, Prentice-Hall, 1986.
The popularity of UNIX based systems and the rapid growth of technology place greater demands on systems designers and hardware vendors to build faster systems to handle accelerated true color graphics applications, including combined audio, video, graphics and text information in a single display (generally called "multimedia" applications), advanced telecommunications applications including voice processing which requires rapid processing, and other kinds of applications combining real-time requirements with the normal time-sharing demands. Attempts to meet these demands to date have included the implementation of distributed computer networks, faster uniprocessor systems, faster and more densely integrated tightly-coupled multiprocessor architectures, and methods to enhance user application processing such as multi-threading user processes.
Multiprocessor hardware availability allows applications to be restructured to make use of more than one processor (CPU) at a time. This requires additional control mechanisms to synchronize the different parts of an application which might be running simultaneously on two or more CPUs. Such new programming capabilities are generally embodied in the new programming paradigm called "multi-threading." A "thread of control" or more simply a "thread" is a sequence of instructions being executed in a program. A thread has a program counter (PC) and a stack to keep track of local variables and return addresses. Threads execute independently. Threads share the process instructions and most of its data, as well as share most of the operating system state of a process. Each thread may make arbitrary system calls. Threads and the associated control and services of a multithreaded system (including synchronization services) may be implemented as objects. Synchronization techniques which are implemented as objects include mutual exclusion (mutex) locks, semaphores, condition variables, and readers/writer locks. For more information on multithreads as applied to application programs, see the paper titled "SunOS Multi-thread Architecture" by M. L. Powell, S. R. Kleiman, S. Barton, D. Shah, D. Stein, M. Weeks, Proceedings of the USENIX Conference-Winter '91--Dallas, Tex., pages 65-79. See also the aforementioned text by Silbershatz et al, at pages 96-97, and 597-629.
In the face of these new demands for multiprocessor support, control of concurrent processing, and support for real-time processing, the simple, time-sharing based UNIX kernel is incapable of supporting tightly-coupled multiprocessing or real-time processing demands. The original UNIX system protects the kernel data structures by two policies: the kernel cannot preempt a process and switch context to another process while executing in kernel mode, and it masks out interrupts when executing a critical region of code if an interrupt handler could corrupt kernel data structures. On a multiprocessor system, however, if two or more processes execute simultaneously in the kernel on separate processors, the kernel could become corrupt in spite of the protective measures that suffice for uniprocessor systems. New operating systems provide a redesigned kernel which can accommodate these requirements. Some of these designs extend the multithreading technique to the kernel, and this in combination with new synchronization techniques, priority setting mechanisms, task scheduling and dispatching rules, allows for maintaining the data integrity of all necessary structures, and the concurrency of simultaneously executing threads. Within such systems, the demands of real-time applications for predictable and bounded response to real-time stimuli, require the incorporation of unique interrupt handling techniques which minimize the overall response time to an interrupt triggering event. The unique design of the present invention provides interrupt handling procedures using kernel threads which satisfies these requirements.
In the present invention, the philosophy is to capture all asynchronous processing in the concept of a kernel thread. Interrupts, since they are a form of asynchronous processing, are handled as threads. While other systems break up the interrupt handling into a part that is a thread and a part that is a non-thread interrupt handler, the present invention executes the interrupt handling entirely as a thread. In order to do this efficiently, the invention delays expensive processing, such as context switching until it is absolutely necessary to do so. Moreover, additional processing efficiency is gained by the use of pre-prepared interrupt handler threads. By handling the entire interrupt as a thread, the remainder of the kernel can synchronize with these interrupt handler threads without locking interrupts out for an unbounded period of time. As a result, the periods that interrupts are locked out are few in number and bounded in time. In addition, synchronizing with interrupt handler threads does not require the raising and lowering of the CPU interrupt priority level, which also saves significant processing time.
As a result of using interrupt handler threads for the entire interrupt processing task, and as a result of the fact that these threads may be blocked by other threads, priority inversion is possible (i.e., a lower priority activity blocking a higher priority activity). However, in the present invention, such priority inversion is prevented by having the blocked thread give its dispatching priority level to the thread causing the block to insure that the blocking thread runs at the same high level as the blocked thread and does not get stuck behind other lower dispatch priority activities. The blocking thread is said to "inherit the priority" of the blocked thread. This approach provides the rapid and bounded response necessary to permit real-time processing in a multi-processing, multi-threaded environment.
Additional information concerning the implementation of the SunOS 5.0 Operating System may be found in the following articles: Kleiman 1992! S. Kleiman, J. Voll, J. Eykholt, A. Shivalingiah, D. Williams, M. Smith, S. Barton, and G. Skinner, Symmetric Multiprocessing in Solaris 2.0, COMPCON Spring 1992, p181, San Francisco, Calif.; Khanna 1992! Sandeep Khanna, Michael Sebree , John Zolnowsky, Realtime Scheduling in SunOS 5.0, USENIX, Winter 1992, San Francisco, Calif.